//package com.school.chapter02.graph_;
//
//import java.util.Iterator;
//
////队列类，用链表实现,后面有用
//class Queue<T> implements Iterable<T>{
//    //    节点个数，头节点，尾节点
//    private int N;
//    private Node head;
//    private Node last;
//    //节点类
//    public class Node {
//        public T data;
//        public Node next;
//
//        public Node(T data, Node next) {
//            this.data = data;
//            this.next = next;
//        }
//    }
//    //构造方法，初始化
//    public Queue() {
//        this.N = 0;
//        this.head = new Node(null,null);
//        this.last = null;
//    }
//    //队列长度
//    public int size(){
//        return N;
//    }
//    //队列是否为空
//    public boolean isEmpty(){
//        return N==0;
//    }
//    //入队列
//    public void enqueue(T data){
////        如果队列为空，说明尾节点为空，让新节点为尾节点，头借点指向尾节点
//        if (isEmpty()){
//            last=new Node(data,null);
//            head.next=last;
////            如果队列不为空，让新节点为尾节点，老的尾节点指向新尾节点
//        }else {
//            Node oldlast=last;
//            last=new Node(data,null);
//            oldlast.next=last;
//        }
////        最后元素+1
//        N++;
//    }
//    //出队列，注意先入先出，每次出的节点就是head指向的第一个节点，然后让head只想第二个节点即可
////    且注意，如果队列为空，要将last=null
//    public T dequeue(){
////        如果为空，返回null
//        if (isEmpty()){
//            return null;
////            如果不为空，让head只想第二个节点，元素-1，且如果队列为空，要将last=null
//        }else {
//            Node oldfirst=head.next;
//            head.next=oldfirst.next;
//            N--;
//
//            if (isEmpty()){
//                last=null;
//            }
////            返回弹出的元素
//            return oldfirst.data;
//        }
//    }
//
//    //    遍历
//    @Override
//    public Iterator iterator() {
//        return new QIterator();
//    }
//    //    创建一个内部类实现Iterator接口
//    public class QIterator implements Iterator {
//        //        定义一个遍历的节点
//        private Node n;
//
//        public QIterator() {
////            初始化为0索引位置
//            this.n = head;
//        }
//
//        //重写两个方法
//        @Override
//        public boolean hasNext() {
////            这个方法判断是否超出最大索引，如果超出会停止遍历
//            return n.next != null;
//        }
//
//        @Override
//        public Object next() {
////            这个方法会遍历得每个节点
//            n = n.next;
//            return n.data;
//        }
//    }
//}
//
//class Graph{
//    private int V;//顶点数
//    private int E;//边数
//    private String[] adj;//邻接表，用于装每个顶点的相连的顶点组成的队列,注意索引是每个顶点，这个索引对应的值是相连的顶点组成的队列
//    //adj中索引是每个顶点，为了在图中可以添加任意类型的数据，比如城市名字，字母等，因此使用一个数组将索引映射为其他数据
//    //比如讲索引0，映射为A
//    private String[] mapArr;
//    //构造方法，传入顶点个数，初始化边数为0，
//    public Graph(int v) {
//        this.V = v;
//        this.E=0;
//        this.adj=new String[v];//初始化队列数组，大小为顶点的个数
//        for (int i = 0; i <adj.length ; i++) {
//            adj[i]=null;//初始化数组的每个队列
//        }
//        //初始化mapArr，在初始情况下，每个索引对应的顶点元素为null
//        this.mapArr = new String[v];//注意不能new T[v]
////        for (int i = 0; i <mapArr.length ; i++) {
////            mapArr[i]=null;
////        }
//    }
//
//    //添加顶点，和索引对应
//    public void addV(int i,String v){
//        mapArr[i]=v;
//    }
//
//    //获得顶点的个数
//    public int getV(){
//        return V;
//    }
//
//    //获取顶点在邻接表内所对应的索引
//    public int getIndex(String v){
//        for (int i = 0; i <mapArr.length ; i++) {
//            if (mapArr[i]==v){
//                return i;
//            }
//        }
//        return -1;
//    }
//    //添加边，即将顶点v，w连接起来形成图，注意是无向的因此不仅要adj[getIndex(v)].enqueue(w);还要adj[getIndex(w)].enqueue(v);
//    public void addEdge(String v, String w){
//        adj[getIndex(v)] = w;
//        adj[getIndex(w)] = v;
//        E++;//边数+1
//    }
//
//    //    获取边的个数
//    public int getE(){
//        return E;
//    }
//
//    //获取某个顶点相邻的所有顶点，返回这个队列即可
//    public String getAdj(String v){
//        return adj[getIndex(v)];
//    }
//}
////测试
//public class MyJava {
//
//    public static void main(String[] args) {
//        Graph graph=new Graph(5);
//        //添加顶点
//        graph.addV(0,"A");
//        graph.addV(1,"B");
//        graph.addV(2,"C");
//        graph.addV(3,"D");
//        graph.addV(4,"E");
//
//        //添加边
//        graph.addEdge("A","B");
//        graph.addEdge("A","C");
//        graph.addEdge("A","D");
//        graph.addEdge("B","C");
//
//        System.out.println("顶点个数:"+graph.getV());
//        System.out.println("边条数:"+graph.getE());
//        System.out.print("顶点A相邻元素包括:");
//        int[] vs=graph.getAdj("A");
//        for (Object v : vs){
//            System.out.print(v+" ");
//        }
//    }
//}
//
